競技プログラミングでバグった時のためのチェックリスト：セグ木

注目して検証すべき場所

セグ木配列の要素

セグ木配列の添字

比較関数はテストしたか？

大小の比較対象は存在するか？

存在しない場合、SEGVを起こす可能性がある。

初期化

segtree配列の葉の数はlower_boundで得たか？

code:cpp

assert(lower_bound(1 << 5 - 1) == 1 << 5);

assert(lower_bound(1 << 5 ) == 1 << 5);

assert(lower_bound(1 << 5 + 1) == 1 << 6);

segtree配列の配列長は、lower_boundで得られた要素をさらに二倍したのち-1したか？

0b0111は3段の完全2分木のノード数を表している。

このときlower_boundで得られるのは0b0100なので、2倍して1引くと0b0111になる。

配列Aの入力

i in [0, |A|)か？

segtreeの添字jはj in [size/2, size/2 + |A|)か？

sizeはsegtree配列の長さ。

j in [size/2, size)ではない。

code:cpp

for (size_t i = 0; i < tmp.size(); i++) {

// #FIXED iがsize/2からsizeにまで渡って初期化されていた（範囲外エラー）

// -> iはtmp.size()までしか行かないようにした。

segtreei + size / 2 = {tmpi, 1, -1, 0 };

}

書き換えクエリ

0-originのとき、

親参照において、割られる数はcurrent_nodeではなくcurrent_node-1か？

code:cpp

current = (current-1)/2;

segtreecurrent = compare(segtreel(current), segtreer(current));

do-whileの繰り返しにおいて、current > 0か？

無限ループの恐れあり

問い合わせクエリ

l, rがクエリの内容、a, bがノードnodeの示す範囲か？

初期値のbは0, A.size()と与えたくなるが、実際には空白の葉ノードが補填されている可能性がある

与えるべきは、lower_bound(A.size())または、(segtree.size() + 1) / 2